package leetcode_21_40;

import utils.ListNode;

public class reverseKGroup_25 {
    /**
     * 思路是逐段切割链表
     * 再反转链表,拼接到一起
     * 0ms ,感觉自己是天才
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode result=new ListNode();
        ListNode root=result;
        ListNode  curr = head;
        flag:while (curr != null){
            ListNode temp=curr;                                   //先用temp保存剩余的链表
            for (int j = 0; j < k - 1; j++) {
                if(curr.next==null){          //如果剩下的节点不够k，不再进行反转操作
                   root.next=temp;
                    break flag;
                }
                curr = curr.next;
            }
            ListNode next = curr.next;                            //保存好下一个节点
            curr.next = null;                                             //断开联系
            root.next=reverseList(temp);                     //添加反转后的链表
            while(root.next!=null)
                root=root.next;
            curr = next;                                                    //让curr指向下一个节点
        }
        return result.next; // 返回新链表的头节点
    }

    /**
     * 反转链表
     * @param node
     * @return
     */
    public static ListNode reverseList(ListNode node){
        ListNode pReversedHead = null; //反转过后的单链表存储头结点
        ListNode pNode = node; //定义pNode指向pHead;
        ListNode pPrev = null; //定义存储前一个结点
        while(pNode != null){
            ListNode pNext = pNode.next; //定义pNext指向pNode的下一个结点,同时保存这node的剩余节点
            if(pNext==null){ //如果pNode的下一个结点为空，则pNode即为结果
                pReversedHead = pNode;
            }
            pNode.next = pPrev;           //修改pNode的指针域指向pPrev，此时node.next 跟随 pPre变为null
            pPrev = pNode;                   //将pNode结点复制给pPrev
            pNode = pNext;                  //将pNode的下一个结点复制给pNode
        }
        return pReversedHead;

    }

    /**
     * 看到的简洁算法
     * 0ms
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup2(ListNode head, int k) {
        ListNode dummy = new ListNode(0), prev = dummy, curr = head, next;
        dummy.next = head;
        int length = 0;
        while(head != null) {
            length++;
            head = head.next;
        }
        head = dummy.next;
        for(int i = 0; i < length / k; i++) {
            for(int j = 0; j < k - 1; j++) {
                next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
            curr = prev.next;
        }
        return dummy.next;
    }
}
